백준 13544번

오늘 풀어본 문제는 백준의 13544번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 7

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

길이가 $N$ 인 수열 $A_1,\ A_2,\ \cdots,\ A_N$ 이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

$i\ j\ k$: $A_i,\ A_{i+1},\ \cdots,\ A_j$ 로 이루어진 부분 수열 중에서 $k$ 보다 큰 원소의 개수를 출력한다.

입력

첫째 줄에 수열의 크기 $N$ $(1 \le N \le 100,000)$ 이 주어진다.

둘째 줄에는 $A_1,\ A_2,\ \cdots,\ A_N$ 이 주어진다. $(1 \le A_i \le 109)$

셋째 줄에는 쿼리의 개수 $M$ $(1 \le M \le 100,000)$ 이 주어진다.

넷째 줄부터 $M$ 개의 줄에는 $a, b, c$ 가 주어진다. $a, b, c$ 를 이용해 쿼리를 만들어야 한다.

$i = a\ \text{xor}\ \text{last_ans}$
$j = b\ \text{xor}\ \text{last_ans}$
$k = c\ \text{xor}\ \text{last_ans}$

last_ans는 이전 쿼리의 정답이며, 가장 처음에는 $0$ 이다. xor한 결과는 $1 \le i \le j \le n,\ 1 \le k \le 10^9$ 을 만족한다.

출력

각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다.

풀이과정

1번째 시도

문제를 가만히 보니 그냥 백준 13537번(수열과 쿼리 1) 문제에서 쿼리 입력 부분만 조금 손보면 똑같다는 것을 알 수 있었다! 그래서 예전에 푼 코드를 그대로 가져와서 조금 수정만 해서 제출하기로 하였다.

코드는 다음과 같이 작성하였다. 제출할 때는 헤더파일의 코드를 붙여넣어 제출하였다.

merge_sort_tree.hpp

#ifndef __MERGE_SORT_TREE_HPP__
#define __MERGE_SORT_TREE_HPP__

template <typename T>
class MergeSortTree {
private:
    std::vector<std::vector<T>> tree;
    std::vector<T> arr;
    size_t n;

    void build(size_t idx, size_t left, size_t right) {
        if (left == right) {
            tree[idx].resize(1);
            tree[idx][0] = arr[left];
            return;
        }

        size_t mid = (left + right) / 2;

        build(2 * idx, left, mid);
        build(2 * idx + 1, mid + 1, right);

        tree[idx].resize(tree[2 * idx].size() + tree[2 * idx + 1].size());
        std::merge(tree[2 * idx].begin(), tree[2 * idx].end(),
            tree[2 * idx + 1].begin(), tree[2 * idx + 1].end(),
            tree[idx].begin());
    }

    size_t query(size_t i, size_t j, const T& k, size_t node, size_t currentLeft, size_t currentRight) {
        size_t result;

        if (j < currentLeft || currentRight < i) {
            result = 0;
        }
        else if (i <= currentLeft && currentRight <= j) {
            result = tree[node].end() - upper_bound(tree[node].begin(), tree[node].end(), k);
        }
        else {
            size_t mid = (currentLeft + currentRight) / 2;
            result = query(i, j, k, 2 * node, currentLeft, mid) + query(i, j, k, 2 * node + 1, mid + 1, currentRight);
        }

        return result;
    }

public:
    MergeSortTree(const std::vector<T>& a) : arr(a), n(a.size()) {
        tree.resize(4 * n + 1);
        build(1, 0, n - 1);
    }

    size_t query(size_t i, size_t j, const T& k) {
        return query(i, j, k, 1, 0, n - 1);
    }
};

#endif // __MERGE_SORT_TREE_HPP__

main.hpp

#include <bits/stdc++.h>
#include "merge_sort_tree.hpp"

using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N;

	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	MergeSortTree<int> mst(A);
    int last_ans = 0;
    
	cin >> M;

	for (int query = 0; query < M; query++) {
		int a, b, c;
		cin >> a >> b >> c;

        int i = a ^ last_ans;
        int j = b ^ last_ans;
        int k = c ^ last_ans;
        
        cout << mst.query(i - 1, j - 1, k) << "\n";
	}

	return 0;
}

실행 결과 ‘틀렸습니다’ 가 떴다.

2번째 시도

코드를 다시 보니 last_ans 변수를 업데이트 해주는 걸 깜빡했다는 걸 바로 알 수 있었다.

코드는 다음과 같이 수정하였고, main.cpp 파일만 수정하였다.

main.cpp

#include <bits/stdc++.h>
#include "merge_sort_tree.hpp"

using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N;

	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	MergeSortTree<int> mst(A);
	int last_ans = 0;

	cin >> M;

	for (int query = 0; query < M; query++) {
		int a, b, c;
		cin >> a >> b >> c;

		int i = a ^ last_ans;
		int j = b ^ last_ans;
		int k = c ^ last_ans;

		last_ans = mst.query(i - 1, j - 1, k);

		cout << last_ans << "\n";
	}

	return 0;
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

원래 내가 이 문제를 풀려고 했던 의도는 merge sort tree가 segment tree의 일종이라는 것을 깨달았고, 모노이드를 적절하게 구성하여 merge sort tree 를 사용해야 하는 문제를 풀어보려고 했던 것이다. 그런데 이미 잘 짜둔 코드가 있어서 그냥 사용하게 되었고, 여기서 원래 사용하려던 방법을 간단히 이야기 해보려고 한다.

우선 merge sort tree 는 전체 수열에서 특정 구간의 정렬된 수열을 쿼리로 반환하게 되는데, 이 때 우리는 모노이드의 원소, 연산, 항등원을 다음과 같이 구성할 수 있다.

원소: 전체 수열에 들어갈 수 있는 각 수들의 집합의 power set이 이 모노이드의 원소로 사용된다.
연산: merge sort 에서 정렬된 두 부분 수열을 합치는 연산을 수행한다. 이 연산은 닫혀있고, 결합 법칙이 성립한다.
항등원: 텅 빈 배열이 항등원이 된다. 어떤 부분 수열과 merge 연산을 적용하여도 그 부분 수열이 그대로 나오게 되어 항등원임을 알 수 있다.

원래는 이런 방식으로 모노이드를 구성해서 풀려고 했던 것이다. ~~Actual implementation is left as an exercise to the reader.~~

내가 만든 머지 소트 자료구조는 내 레포지토리²에서 확인할 수 있다. 다만 앞으로 머지 소트 트리를 구현할 때는 세그먼트 트리에 적절한 모노이드를 만드는 방식으로 구현할 것이다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/13544
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/13544/merge_sort_tree.hpp

← Previous Post Next Post →